﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace ai_assignment_2
{
    class nQueen
    {
        private int[] columns;
        private int N;
        private Queue<State> states;
        private List<string> queens;
        private int nrSolutions;
        private List<State> solutions;
        private int nrStates;

        public nQueen(int size)
        {
            N = size;
            columns = new int[N];
            states = new Queue<State>();
            queens = new List<string>();
            solutions = new List<State>();
            for (int i = 0; i < N; i++)
            {
                columns[i] = 0;       
            }
        }

        private void DistQueen(int startState)
        {
            //starting state
            State start = new State(N);
            states.Enqueue(start);

            //While there are states in the queue we continue
            while (states.Count != 0)
            {
                //Take out the current state from the queue
                State current = states.Dequeue();
                nrStates++;
                if (current.isEnd())//if we are in the end we stop and add solution to list
                {
                    solutions.Add(current);
                    current.printState();
                    nrSolutions++;
                }
                //Add states that are near the current state to the queue
                foreach (State s in current.getStatesForDistance())
                {
                    states.Enqueue(s);
                }
            }
        
        
        }

        private void BFSQueen(int startState)
        {
            //starting state
            State start = new State(N);
            states.Enqueue(start);

            //While there are states in the queue we continue
            while (states.Count != 0)
            {
                //Take out the current state from the queue
                State current = states.Dequeue();
                nrStates++;
                if (current.isEnd())//if we are in the end we stop and add solution to list
                {
                    solutions.Add(current);
                    current.printState();
                    nrSolutions++;
                }
                //Add states that are near the current state to the queue
                foreach (State s in current.getStates())
                {
                    states.Enqueue(s);              
                }
            }
        }
        private void DFSQueen(int i)
        {   
                //Check if the position of the queen is valid
                if (place(i-1))
                {
                    nrStates++;
                    //If we get to the end we count the solutions
                    if (i == N)
                    {
                        nrSolutions++;
                        printOutcome();
                    }
                    else
                    {   
                        //Loop and mark the queens in the array
                        for (int j = 0; j < N; j++)
                        {
                            columns[i] = j;
                            DFSQueen(i + 1);
                        }
              
                    }
                }
        }
        //Print out
        void printOutcome()
        {
            for (int i = 0; i < N; i++)
            {
                Console.WriteLine(String.Format("Queen {0}.{1}", i+1, columns[i]+1));           
            }
            Console.WriteLine();       
        }

        private bool place(int i)
        {
            for (int k = 0; k < i; k++)
            {
                if ((columns[i] == columns[k]) || (Math.Abs(columns[i] - columns[k]) == Math.Abs(k - i)))
                    return false;          
            }
            return true;
        }
        //start program and return number of states
        public int[] placeNQueens(string search)
        {           
            if(search.Equals("DFS"))
                DFSQueen(0);
            if (search.Equals("BFS"))
                BFSQueen(0);
            if (search.Equals("Dist"))
                DistQueen(0);
                
            int[] arr = new int[2];
            arr[0] = nrSolutions;
            arr[1] = nrStates;
            return arr;
        }
    }
}
